package com.example.Arithmetic.Arithmetic;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 日期：2023/12/28
 * 时间：8:51
 * 描述：计数排序
 * 记录元素出现次数,允许负数出现
 */
public class CountingSort {
    public void sort(int[] ints) {
        int max = ints[0];
        int min = ints[0];
//        找出最大值和最小值，创建数组
        for (int i = 1; i < ints.length; i++) {
            if (ints[i] > max) {
                max = ints[i];
            }
            if (ints[i] < min) {
                min = ints[i];
            }
        }
        int[] maxint = new int[max - min + 1];
        for (int v : ints) {
            maxint[v - min]++;
        }
        int k = 0;
//        i代表元素当前值，需要减去最小值，也代表原始数组出现个数
        for (int i = 0; i < maxint.length; i++) {
            while (maxint[i] > 0) {
//                i加减min实测没区别
                ints[k++] = i - min;
                maxint[i]--;
            }
        }
    }

    @Test
    public void test() {
        int[] a = new int[1000000];
        int i = 0;
        Random random = new Random();
        while (i < 1000000) {
            int i1 = random.nextInt(100);
            a[i] = i1;
            i++;
        }
        System.out.println(Arrays.toString(a));
        CountingSort countingSort = new CountingSort();
        countingSort.sort(a);
        System.out.println(Arrays.toString(a));
    }
}
